const merge = (arr, l, mid, r) => {
  // 拷贝一份
  const tempArr = arr.slice(l, r + 1);
  let i = l;
  let j = mid + 1;
  for(let k = l; k <= r; k++) {
  	if(i > mid) {
      arr[k] = tempArr[j - l];
      j++;
    } else if (j > r) {
      arr[k] = tempArr[i - l]
      i++
    } else if (tempArr[i - l] < tempArr[j - l]) {
    	arr[k] = tempArr[i - l];
      i++
    } else {
      arr[k] = tempArr[j - l];
      j++
    }
    
  }
}
const _mergeSort = (arr, l, r) => {
	if(l >= r) return; // 说明数组中只有一个元素或者是空
  const mid = l + Math.floor((r - l) / 2);
  _mergeSort(arr, l, mid);
  _mergeSort(arr, mid + 1, r);
  // 此时[l, mid]已经是排好序的，[mid + 1, r]也是排好序的
  if(arr[mid] > arr[mid + 1]) {
    merge(arr, l, mid, r);
  }
}
const mergeSort = (arr) => {
	_mergeSort(arr, 0, arr.length - 1)
}

function generateArr(num, end) {
  const arr = [];
  for (let i = 0; i < num; i++) {
    // eslint-disable-next-line no-unused-expressions
    arr[i] = Math.floor(Math.random() * end);
  }
  return arr;
}
const arr = generateArr(20, 100);
console.log(arr);
mergeSort(arr);
console.log(arr);